package dayPractice;

import java.util.Scanner;

/**
 *
 * 回文数是指数字从前往后读和从后往前读都相同的数字。
 *
 * 例如数字 12321 就是典型的回文数字。
 *
 * 现在给定你一个整数 B，请你判断 1∼300 之间的所有整数中，有哪些整数的平方转化为 B 进制后，其 B 进制表示是回文数字。
 *
 * 输入格式
 * 一个整数 B。
 *
 * 输出格式
 * 每行包含两个在 B 进制下表示的数字。
 *
 * 第一个表示满足平方值转化为 B 进制后是回文数字那个数，第二个数表示第一个数的平方。
 *
 * 所有满足条件的数字按从小到大顺序依次输出。
 *
 * 数据范围
 * 2≤B≤20,
 * 对于大于 9 的数字，用 A 表示 10，用 B 表示 11，以此类推。
 * @author Summerday
 */
public class Main1346回文进制 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // k进制
        int k = sc.nextInt();
        for (int num = 1; num <= 300; num++) {
            String res = base(num * num, k);
            if (isValid(res)) {
                System.out.println(base(num, k) + " " + res);
            }

        }
    }

    private static String base(int num, int k) {
        StringBuilder res = new StringBuilder();
        while (num > 0) {
            res.append(get(num % k));
            num /= k;
        }
        return res.reverse().toString();
    }

    private static char get(int x) {
        if (x <= 9) return (char) (x + '0');
        return (char) (x - 10 + 'A');
    }
    // 判断是否为回文串
    private static boolean isValid(String num) {
        char[] chs = num.toCharArray();
        int i = 0, j = chs.length - 1;
        while (i < j) {
            if (chs[i] != chs[j]) return false;
            i++;
            j--;
        }
        return true;

    }

}
